package 八树结构基础;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/25 20:00
 * 顺序二叉树
 *
 * 1) 顺序二叉树通常只考虑完全二叉树
 * 2) 第 n 个元素的左子节点在数组中为 2 * n + 1
 * 3) 第 n 个元素的右子节点在数组中为 2 * n + 2
 * 4) 第 n 个元素的父节点为 在数组中(n-1) / 2
 * 5) n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)
 */
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(array);

        System.out.println("前序遍历"); //
        arrBinaryTree.preOrder();
        System.out.println("中序遍历");
        arrBinaryTree.infixOrder(); //
        System.out.println("后序遍历");
        arrBinaryTree.postOrder(); //
    }
}

class ArrBinaryTree {
    int array[];

    public ArrBinaryTree(int[] array) {
        this.array = array;
    }

    public void preOrder() {
        this.preOrder(0);
    }

    //前序遍历
    public void preOrder(int index) {
        if (array == null || array.length < 0) {
            System.out.println("空数组无法遍历");
            return;
        }
        System.out.println(array[index]);
        //左遍历
        if ((2 * index) + 1 < array.length) {
            this.preOrder((2 * index) + 1);
        }
        //右遍历
        if ((2 * index) + 2 < array.length) {
            this.preOrder((2 * index) + 2);
        }
    }

    public void infixOrder() {
        this.infixOrder(0);
    }

    //中序遍历
    public void infixOrder(int index) {
        if (array == null || array.length < 0) {
            System.out.println("空数组无法遍历");
            return;
        }
        //左遍历
        if ((2 * index) + 1 < array.length) {
            this.infixOrder((2 * index) + 1);
        }
        System.out.println(array[index]);


        //右遍历
        if ((2 * index) + 2 < array.length) {
            this.infixOrder((2 * index) + 2);
        }
    }

    public void postOrder() {
        this.postOrder(0);
    }

    //后序遍历
    public void postOrder(int index) {
        if (array == null || array.length < 0) {
            System.out.println("空数组无法遍历");
            return;
        }
        //左遍历
        if ((2 * index) + 1 < array.length) {
            this.preOrder((2 * index) + 1);
        }
        //右遍历
        if ((2 * index) + 2 < array.length) {
            this.preOrder((2 * index) + 2);
        }

        System.out.println(array[index]);

    }
}